前言

在對稱密碼學中，我們徹底解決了資料的機密性與完整性問題。然而，對稱密碼學存在一個天生的架構瓶頸——金鑰分配問題（Key Distribution Problem）。若 N 個節點需要兩兩安全通訊，全網需要維護 O(N^2) 把對稱金鑰，且如何在不安全的通道上首次安全地傳遞這把金鑰，形成了一個「雞生蛋、蛋生雞」的難題。

1977 年，Ron Rivest、Adi Shamir 與 Leonard Adleman 提出了著名的 RSA 演算法，正式開啟了非對稱密碼學（Public-Key Cryptography）的時代。RSA 利用單向陷門函數（Trapdoor One-Way Function）的數學特性，將金鑰拆分為公開金鑰（Public Key）與私有金鑰（Private Key），使通訊雙方無需事先共享秘密即可完成安全通訊。

一、 RSA 金鑰生成五步法 (Key Generation)

RSA 的核心建立在質數運算與同餘代數上。其金鑰生成流程如下：

[ 選擇兩個超大質數 p, q ] ───> n = p * q
                               │
                               ▼
                    φ(n) = (p - 1) * (q - 1)
                               │
                               ▼
                     選擇 e (通常為 65537)
                               │
                               ▼
                   計算 d ≡ e⁻¹ (mod φ(n))
                               │
             ┌─────────────────┴─────────────────┐
             ▼                                   ▼
   【公鑰 Public Key】                  【私鑰 Private Key】
        (e, n)                              (d, n)

1. 選擇質數：挑選兩個足夠大且互不相等的隨機質數 p 與 q。
2. 計算模數：計算乘積 n = p * q。n 的位元長度（如 2048 bits）即為 RSA 的金鑰長度。
3. 計算歐拉總額函數（Euler's Totient Function）：

φ(n) = (p - 1)(q - 1)

4. 選擇公鑰指數 e：選擇一個整數 e，滿足 1 < e < φ(n) 且 \gcd(e, φ(n)) = 1（即 e 與 φ(n) 互質）。現代工程標準通常固定選用 Fermat 數 F_4 = 65537 (2^{16} + 1)。
5. 計算私鑰指數 d：計算 e 模 φ(n) 的模反元素（Modular Multiplicative Inverse）d，使其滿足：

e * d ≡ 1 mod{φ(n)}

• 公開金鑰（Public Key）：包含 (e, n)，可公開給任何人用於加密或驗簽。
• 私有金鑰（Private Key）：包含 (d, n)（以及嚴格保密的 p, q, φ(n)），必須嚴密保管於伺服器或 HSM 中。

二、 加解密數學公式與玩具數值演練

1. 抽象運算公式

假設明文訊息為一小於 n 的正整數 m（即 m ∈ Z_n）：

• 加密運算 (Encryption)：傳送方使用接收方的公鑰 (e, n) 計算密文 c：

c ≡ m^e mod n

• 解密運算 (Decryption)：接收方使用自己的私鑰 (d, n) 進行推算，還原出明文 m：

m ≡ c^d mod n

2. 小型數值範例演練 (Toy Example)

• Step 1: 選定質數 p = 61, q = 53。
• Step 2: 計算 n = 61 * 53 = 3233。
• Step 3: 計算 φ(n) = (61 - 1)(53 - 1) = 60 * 52 = 3120。
• Step 4: 選擇 e = 17（與 3120 互質）。
• Step 5: 使用擴展歐幾里得演算法計算 d：

17 * d ≡ 1 mod 3120 => d = 2753

(核對：17 * 2753 = 46801 = 15 * 3120 + 1)

測試加解密：假設明文數字 m = 65

• 加密：c = 65^17 mod 3233 = 2790
• 解密：m = 2790^2753 mod 3233 = 65 (成功還原原始明文)

三、 RSA 的安全性基石與大質數分解難題

RSA 的安全性建立在大整數分解難題（Integer Factorization Problem, IFP）的算力複雜度之上：

已知 p, q  ───────── 很容易 (正向乘法 O(N²)) ─────────> 已知 n
已知 n     ───────── 極度困難 (反向因數分解) ─────────> 推導出 p, q

1. 破解路徑：攻擊者若想透過公開的公鑰 (e, n) 算出私鑰 d，必須先計算出 φ(n) = (p-1)(q-1)。而要得到 φ(n)，前提是必須將 n 分解回 p * q。
2. 算力不對稱性：正向將兩個 1024-bit 的大質數相乘只需要微秒等級；但要反向將一個 2048-bit 的合數 n 分解為 p 與 q，目前最快的數體篩法（General Number Field Sieve, GNFS）在古典電腦上需要耗費數百萬年的算力。

現代安全金鑰長度建議

四、 Java JCA 生產級 RSA 金鑰對生成實作

以下展示如何使用標準 Java JCA API 生成安全長度（2048/3072 bits）的 RSA KeyPair，並導出其數學參數：

import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.interfaces.RSAPrivateCrtKey;
import java.security.interfaces.RSAPublicKey;

public class RsaKeyPairGeneratorExample {

    private static final String ALGORITHM = "RSA";
    private static final int KEY_SIZE_BITS = 3072; // 採用 3072 bits 高安全強度

    public static void main(String[] args) throws Exception {
        System.out.println("正在生成 " + KEY_SIZE_BITS + "-bit RSA 金鑰對...");

        // 1. 初始化 KeyPairGenerator
        KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(ALGORITHM);
        keyPairGen.initialize(KEY_SIZE_BITS);

        // 2. 生成金鑰對
        KeyPair keyPair = keyPairGen.generateKeyPair();
        PublicKey pubKey = keyPair.getPublic();
        PrivateKey privKey = keyPair.getPrivate();

        // 3. 提取 RSA 公鑰數學參數 (e, n)
        if (pubKey instanceof RSAPublicKey rsaPubKey) {
            System.out.println("\n--- RSA 公鑰 (Public Key) ---");
            System.out.println("Modulus (n) 位元長度: " + rsaPubKey.getModulus().bitLength() + " bits");
            System.out.println("Public Exponent (e): " + rsaPubKey.getPublicExponent());
        }

        // 4. 提取 RSA 私鑰數學參數 (d, n)
        if (privKey instanceof RSAPrivateCrtKey rsaPrivKey) {
            System.out.println("\n--- RSA 私鑰 (Private Key - CRT 格式) ---");
            System.out.println("Private Exponent (d) 位元長度: " + rsaPrivKey.getPrivateExponent().bitLength() + " bits");
            System.out.println("Prime p 位元長度: " + rsaPrivKey.getPrimeP().bitLength() + " bits");
            System.out.println("Prime q 位元長度: " + rsaPrivKey.getPrimeQ().bitLength() + " bits");
        }

        System.out.println("\n 安全 RSA 金鑰對生成成功！");
    }
}